class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> tmp(nums.size()); //这个地方非常重要，放到外层和内层将省去很多的时间
        SortMerge(nums,0,nums.size()-1,tmp);
        
        return nums;
    }
    //merge要做的事情是什么，把左右两侧的合起来
    void Merge(vector<int>& arr,int l,int mid,int r,vector<int>& tmp)
    {
        int i = l;
        int j = mid + 1;

        int t = 0;

        
        
        while (i <= mid && j <= r)
        {
            if (arr[i] <= arr[j])
            {
                tmp[t++] = arr[i++];
            }
            else
            {
                tmp[t++] = arr[j++];
            }
        }

        //遍历完开始处理左右两侧剩下的
        while (i <= mid)
        {
            tmp[t++] = arr[i++];
        }

        while (j <= r)
        {
            tmp[t++] = arr[j++];
        }
        t = 0;
        //拷贝回去
        while (l <= r)
        {
            arr[l++] = tmp[t++];
        }

    }

    void SortMerge(vector<int>& arry,int l,int r,vector<int>& tmp)
    {
        if (l < r)
        {


        int mid = (r - l) / 2 + l;
        SortMerge(arry, l, mid,tmp);
        SortMerge(arry, mid + 1, r,tmp);
        Merge(arry, l, mid, r,tmp);
        }

    }

};